[UOJ455]-雪灾与外卖

传送门

感觉这题好神啊，可撤销贪心什么的傻傻想不明白，模拟费用流也太高级了吧

---

复习一下网络流

注意反悔边

如果裸的跑，即 EK，会 T，$O(nm^2)$

优化就是在最短路上跑，（更准确地说是保留在原来的残量网络中可以被增广的边即连的点）dinic，$O(n^2m)$

---

回到本题

裸的费用流 或者 根据贪心用单调队列做 是 25 分

正解是用可撤销贪心来模拟费用流（什么）

学习了这篇博客

重点在于模拟退流，即反悔操作

考虑将人和餐厅按坐标排序，从左往右做，维护两个堆分别储存人和餐厅的贡献们

先忽略 $c$ 的限制，即将餐厅拆点

对于人，把它与左边最优的餐厅匹配，贡献是 $x_i + v_j$, 其中 $v_j$ 是左边餐厅的贡献

如果人要反悔，贡献就是 $-2x_i - v_j$

注意这里餐厅没有反悔的必要，因为餐厅与人的匹配不会相交，只需要保证人反悔再反悔能匹配上原餐厅就好了

对于餐厅，把它与左边最优的人匹配，贡献是 $y_i + w_i + v_j$，其中 $v_j$ 是左边人的贡献

如果人要反悔，贡献就是 $-y - w$

如果餐厅要反悔，$-v_j - 2y$

这样复杂度是 $O((n + \sum c)log(n + \sum c))$

考虑去掉拆点，发现当前暂时匹配同一个餐厅的人 的反悔贡献是相同的，于是可以把它们压在一起

$O((n + m)log(n + m))$

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;  // 第二位是个数
const int N = 1e5 + 10;
const ll inf = 1e18;
ll n, m, X[N], Y[N], W[N], C[N];
ll ans, tot;
priority_queue<pll, vector<pll>, greater<pll> > A, B;

void push_x(ll x) {
    ll y;
    if (B.empty()) y = inf;
    else y = B.top().first;
    ans += x + y;
    A.push(make_pair(-2 * x - y, 1));
    if (B.size()) {
        ll t = B.top().second;
        B.pop();
        if (t > 1) B.push(make_pair(y, t - 1));
    }
}

void push_y(ll y, ll w, ll c) {
    ll m = 0;
    while (c != m && A.size() && y + w + A.top().first < 0) {
        ll x = A.top().first;
        ll t = A.top().second, tt = min(c - m, t);
        ans += tt * (x + y + w);
        A.pop();
        if (tt != t) A.push(make_pair(x, t - tt));
        B.push(make_pair(-x - 2 * y, tt));
        m += tt;
    }
    if (m) A.push(make_pair(-y - w, m));
    if (c != m) B.push(make_pair(-y + w, c - m));
}

int main() {
    cin >> n >> m;
    rep(i, 1, n) scanf("%lld", &X[i]);
    rep(i, 1, m) scanf("%lld%lld%lld", &Y[i], &W[i], &C[i]), tot += C[i];
    if (tot < n) return puts("-1"), 0;
    int i = 1, j = 1;
    while (i <= n && j <= m) {
        if (X[i] < Y[j]) push_x(X[i]), ++i;
        else push_y(Y[j], W[j], C[j]), ++j;
    }
    while (i <= n) push_x(X[i]), ++i;
    while (j <= m) push_y(Y[j], W[j], C[j]), ++j;
    printf("%lld\n", ans);
    return 0;
}